home *** CD-ROM | disk | FTP | other *** search
/ Languguage OS 2 / Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO / language / embedded / develop / libsrc11.arc / FREE.C < prev    next >
C/C++ Source or Header  |  1989-04-27  |  4KB  |  172 lines
  1. /*    free.c 4.4        */
  2. /*M****************************************************************************
  3.  
  4. MODULE NAME:    free
  5.  
  6. DESCRIPTION:    This module has the free function and the malloc function.
  7.  
  8. ******************************************************************************/
  9. #include <hc11/directives.h>
  10.  
  11.     /************************************************/
  12.     /*    Structures for Free and Malloc        */
  13.     /************************************************/
  14.  
  15.     typedef int ALIGN;        /* align on word boundary */
  16.  
  17.     union header    {        /* free block header */
  18.         struct    {
  19.             union header *ptr;    /* next free block */
  20.             unsigned size;    /* size of this free block */
  21.             }    s;
  22.         ALIGN    x;        /* force alignment of blocks */
  23.         };
  24.  
  25.     typedef union header HEADER;
  26.  
  27. #define        HDR_SIZE    4    /* size of the HEADER structure */
  28. #define        NULL        0    /* null pointer */
  29.  
  30.     /************************************************/
  31.     /*    static variable for Free and Malloc    */
  32.     /************************************************/
  33.  
  34.     static HEADER base;        /* empty list to get started with */
  35.     static HEADER *allocp = NULL;    /* last allocated block */
  36.  
  37.  
  38.  
  39.     /************************************************/
  40.     /*    moreRAM                    */
  41.     /*                        */
  42.     /*    Lops off a chunk of RAM since there    */
  43.     /*    are no appropriately sized pieces    */
  44.     /*    in the fragmented free space (linked    */
  45.     /*    list).                    */
  46.     /************************************************/
  47.  
  48. SMALL
  49.     static HEADER *moreRAM ( chunk_units )
  50.  
  51.         unsigned    chunk_units ;
  52.  
  53. #define        NALLOC    HDR_SIZE    /* number of units to allocate at once */
  54.  
  55.     {
  56.         extern    unsigned l__STKLO ;    /* start of free space */
  57.         static    unsigned free_start = NULL ;
  58.         HEADER    * chunk_ptr ;        /* must be last local variable */
  59.  
  60.     if    (free_start == NULL)
  61.         free_start = (unsigned) &l__STKLO ;
  62.  
  63. #ifdef    HDR_SIZE = 4
  64.     chunk_units = chunk_units << 2 ;
  65. #else
  66.     chunk_units = chunk_units * HDR_SIZE ;
  67. #endif
  68.  
  69.     if    (free_start + chunk_units >= (unsigned) (&chunk_ptr) - 4)
  70.         return ( (HEADER *) NULL ) ;    /* grew into stack... */
  71.  
  72.     if    ( (chunk_units >> 8) + (free_start >> 8) > 255 )
  73.         return ( (HEADER *) NULL ) ;    /* wrapped around memory */
  74.  
  75.     chunk_ptr = (HEADER *) free_start ;
  76.     
  77.     chunk_ptr->s.size = chunk_units ;
  78.  
  79.     free ( (char *) (chunk_ptr + 1) ) ;
  80.  
  81.     return (allocp) ;
  82.  
  83.     }    /* end of moreRAM */
  84.  
  85.  
  86.     /************************************************/
  87.     /*    Malloc function                */
  88.     /************************************************/
  89.  
  90. SMALL
  91.     char    *malloc ( nbytes )    /* general purpose storage allocator */
  92.  
  93.         unsigned    nbytes ;
  94.  
  95.     {
  96.  
  97.         HEADER    *p,*q ;
  98.         int    nunits ;
  99.  
  100. #ifdef    HDR_SIZE=4
  101.     nunits = 1 + ((nbytes + HDR_SIZE - 1) >> 2) ;
  102. #else
  103.     nunits = 1 + ((nbytes + HDR_SIZE - 1)/HDR_SIZE ;
  104. #endif
  105.  
  106.     if    ((q = allocp) == NULL) 
  107.         {        /* no free list */
  108.         base.s.ptr = allocp = q = &base ;
  109.         base.s.size = 0 ;
  110.         }
  111.  
  112.     for ( p = q->s.ptr ;  ; q = p, p = p->s.ptr)
  113.         {
  114.         if    ( p->s.size >= nunits )
  115.             {    /* big enough */
  116.             if    ( p->s.size == nunits )    
  117.                 q->s.ptr = p->s.ptr ;    /* exactly right */
  118.             else    /* remove the extra bits... */
  119.                 {
  120.                 p->s.size -= nunits ;
  121.                 p += p->s.size ;    /* skip over extra bits */
  122.                 p->s.size = nunits ;
  123.                 }
  124.             allocp = q ;
  125.             return ( (char *) (p+1) ) ;
  126.             }
  127.  
  128.         if    (p == allocp)    /* wrapped around free list */
  129.             if    ( (p = moreRAM(nunits)) == NULL)
  130.                 return (NULL) ;        /* none left */
  131.         }    /* end of for loop */
  132.     }    /* end of malloc */
  133.  
  134.  
  135.     /************************************************/
  136.     /*    Free function                */
  137.     /************************************************/
  138.  
  139. SMALL
  140.     free ( ap )        /* put block ap in free list */
  141.  
  142.         char    *ap ;
  143.  
  144.     {
  145.         HEADER *p, *q ;
  146.  
  147.     p = (HEADER *) ap - 1 ;        /* point to header */
  148.  
  149.     for ( q = allocp ; ! (p > q && p < q->s.ptr) ; q = q->s.ptr )
  150.         if    ( q >= q->s.ptr && (p > q || p < q->s.ptr) )
  151.             break ;        /* at one end or other */
  152.  
  153.     if    ( p + p->s.size == q->s.ptr)    /* joint to upper number */
  154.         {
  155.         p->s.size += q->s.ptr->s.size ;
  156.         p->s.ptr = q->s.ptr->s.ptr ;
  157.         }
  158.     else
  159.         p->s.ptr = q->s.ptr ;
  160.  
  161.     if    ( q + q->s.size == p)    /* join to lower number */
  162.         {
  163.         q->s.size += p->s.size ;
  164.         q->s.ptr = p->s.ptr ;
  165.         }
  166.     else
  167.         q->s.ptr = p ;
  168.  
  169.     allocp = q ;
  170.  
  171.     }    /* end of free */
  172.